package demo2;

public class MySingeList {
    public class ListNode{
        public int val;
        public ListNode next;//存放下一个节点的地址
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;//永远指向头节点，因为头节点是链表的属性，不是链表里面每个节点的属性。头节点也是也是链表里面的一个节点
    //创建链表
    public void creatList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }
    //遍历链表
    public void show(){
        ListNode cur = head;//避免head变成null,没法用于后面的方法
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //得到链表的长度
    public int size(){
        ListNode cur = head;
        int count = 0;
        while (cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur!=null){
            //如果val是引用类型，就需要用equals判断是否相等
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if (cur != null) {
            while (cur.next!=null){
                cur = cur.next;
            }
            //此时cur指向的就是尾节点
            cur.next = node;
        }else {
            head = node;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if (index<0||index>this.size()){
            throw new IndexOutException("index输入不合法:"+index);
        }
        if (index == 0){
            this.addFirst(data);
            return;
        }
        if (index == this.size()){
            this.addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
//        ListNode cur = head;
//        for (int i = 0; i < index-1; i++) {
//            cur = cur.next;
//        }//这里注释掉的部分可以直接用下面的findNode直接代替，findNode是写的一个寻找index所在处节点的方法
        ListNode cur = this.findNode(index);
        node.next = cur.next;
        cur.next = node;
    }
    //获取得到index编号的节点（但是需要注意，节点不是用下标，这只是一种解决问题的说法）
    private ListNode findNode(int index){
        ListNode cur = head;
        while (index-1!=0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if (head==null){
            return;
        }
        if (head.val == key){
            head =head.next;
            return;
        }
        ListNode prev = searchPrev(key);//需要删除节点的前一个节点
        if (prev == null){
            System.out.println("没有这个数据！");
            return;
        }
        ListNode del = prev.next;//需要删除的节点
        prev.next = del.next;//删除
    }
    //查找第一次为Key的节点
    private ListNode searchPrev(int key){
        ListNode prev = head;
        while(prev.next!=null){
            if (prev.next.val == key){
                return prev;
            }else{
                prev = prev.next;
            }
        }
        return null;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (head==null){
            return;
        }
        ListNode prev = head;
        ListNode cur = prev.next;
        while(cur!=null){
            if (cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;

            }
        }
        if (head.val == key){
            head = head.next;
        }
    }
     //回收链表
    public void clear() {
//        this.head = null;
        //或者按照以下的方法
        while(head!=null){
            ListNode headNext = head.next;
            head.next = null;
            head = headNext;
        }
    }
    //逆序打印链表---->方式1：递归
    public void show1(ListNode head){
        if (head == null){
            return;
        }
        if (head.next == null){
            System.out.println(head.val);
            return;
        }
        show1(head.next);
        System.out.println(head.val);
    }
    //逆序打印链表---->方式2：使用栈
    public void show2(){
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.empty()){
//            ListNode tmp = stack.pop();
//            System.out.println(tmp.val);
            System.out.println(stack.pop().val);
        }
    //力扣练习题
    //1.给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。----->使用头插发法
    public void reverseList(){
        if (head == null){
            return;
        }
        if (head.next == null){
            return;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
    }
    //2.给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
    //方法：使用快慢指针法，实现时间复杂度为O(N)，空间复杂度为O（1）
    public ListNode middleNode(){
        if (head == null){
            return null;
        }
        if (head.next == null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null&&fast.next!=null){//首先这里的两个判断条件的顺序不能换，因为需要先判断fast！=null 才能保证fast.next不会
            // 出现空指针异常；其次两个判断条件应该使用&&进行连接，因为需要满足下面的fast.next.next不出现空指针异常，
            // 另外两个判断也针对节点数为奇数和偶数两种情况
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    // 3.输入一个链表，输出该链表中倒数第k个结点。
    public ListNode findKthToTail(int K){
        if (K<=0||head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(K-1>0){
            fast = fast.next;
            K--;
            if (fast == null){
                return null;//该if语句就可以省略计算链表的size，避免了时间复杂度的浪费
            }
        }//可以代替下面的for循环
//        for (int i = 0; i < K-1; i++) {
//            fast = fast.next;
//        }
        while (fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    //4.现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在
    // 其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针
    public ListNode partition(int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while(cur!=null){
            if (cur.val<x){
                if (bs == null){
                    bs = cur;
                    be = cur;
//                    cur = cur.next;省略1
                }else{
                    be.next = cur;
                    be = be.next;
//                    cur = cur.next;省略1
                }
//                cur = cur.next;省略2
            }else{
                if (as == null){
                    as = cur;
                    ae = cur;
//                    cur = cur.next;省略1
                }else{
                    ae.next = cur;
                    ae = ae.next;
//                    cur = cur.next;省略1
                }
//                cur = cur.next;省略2
            }
            cur = cur.next;
        }
        if (bs == null){
            return as;
        }
        be.next = as;
        if (as!=null){
            ae.next = null;
        }
        return bs;
    }
    //5.对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
    //给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
    public boolean chkPalindrome() {
        //1.找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow就是中间节点
        //2.将中间节点后面的节点进行翻转
        ListNode cur = slow.next;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.判断是否回文
        while(head!=slow){
            if (head.val!=slow.val){
                return false;
            }
            if (head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    //6.给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null||headB == null){
            return null;
        }
        //思路：只能为Y型。两个链表同时走，走到next同
        //1.判断谁更加长，谁更长谁就先走几步
        ListNode plong = headA;//假设A链表更加长
        ListNode pshort = headB;
        int len1 = 0;
        int len2 = 0;
        while(plong!=null){
            len1++;
            plong = plong.next;
        }
        while(pshort!=null){
            len2++;
            pshort = pshort.next;
        }
        int len = len1 - len2;
        plong = headA;
        pshort = headB;
        if(len<0){
            plong = headB;
            pshort = headA;
            len = len2 - len1;
        }
        //先走len步
        while(len>0){
            plong = plong.next;
            len--;
        }
        //2.一起走,判断相交节点
        while(plong!=pshort){
            plong = plong.next;
            pshort = pshort.next;
        }
        return plong;
    }
    //7.给你一个链表的头节点 head ，判断链表中是否有环。
    public boolean hasCycle() {
        if (head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                return true;
            }
        }
        return false;
    }
    //8.给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
    public ListNode detectCycle() {
        if (head == null || head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next;
            if (slow == fast){
                break;
            }
        }
        if (fast == null || fast.next == null){
            return null;
        }
        fast = head;
        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

}
